#include<iostream>

template <class Data>
class Deque
{
private:
	struct Node{
		Data info;
		Node *next;
	};
	Node *start;
	Node *end;
	unsigned int _size;
	void deleteDeque();
	void copyDeque(const Deque &rhs);
public:
	Deque();
	Deque(const Deque &rhs);
	~Deque();
	Deque &operator =(const Deque &rhs);
	void push_front(const Data &value);
	void push_back(const Data &value);
	bool pop_front(Data& outValue);
	bool pop_back(Data& outValue);
	unsigned int size() const;
	bool isEmpty() const;
};

template <class Data>
Deque<Data>::Deque()
{
	start = NULL;
	end = NULL;
	_size = 0;
}

template <class Data>
Deque<Data>::~Deque()
{
	deleteDeque();
}

template <class Data>
Deque<Data>::Deque(const Deque &rhs)
{
	copyDeque(rhs);
}

template <class Data>
Deque<Data> &Deque<Data>::operator=(const Deque<Data> &rhs)
{
	if (this != &rhs)
	{
		deleteDeque();
		copyDeque(rhs);
	}
	return *this;
}

template <class Data>
void Deque<Data>::push_front(const Data &value)
{
	Node* n = new Node;
	n->info = value;
	n->next = start;
	start = n;
	_size++;
	if (_size == 1)
	{
		end = n;
	}
}

template <class Data>
void Deque<Data>::push_back(const Data &value)
{
	if (isEmpty())
	{
		push_front(value);
	}
	else
	{
		Node* last = end;
		/*while(last->next != NULL)
		{
			last = last->next;
		}*/
		Node* n = new Node();
		n->info = value;
		n->next = NULL;
		last->next = n;
		end = last->next;
		_size++;
	}
}

template <class Data>
bool Deque<Data>::pop_front(Data& out)
{
	if (isEmpty())
	{
		return false;
	}
	out = start->info;
	Node* t = start;
	start = start->next;
	delete t;
	_size--;
	return true;
}

template <class Data>
bool Deque<Data>::pop_back(Data& out)
{
	if (size() <= 1)
	{
		return pop_front(out);
	}
	Node* preLast = start;
	while(preLast->next->next != NULL)
	{
		preLast = preLast->next;
	}
	out = preLast->next->info;
	delete preLast->next;
	preLast->next = NULL;
	_size--;
	return true;
}

template <class Data>
bool Deque<Data>::isEmpty()const
{
	if (_size == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

template <class Data>
unsigned int Deque<Data>::size()const
{
	return _size;
}

template <class Data>
void Deque<Data>::deleteDeque()
{
	Data dummy;
	while(pop_front(dummy));
}

template <class Data>
void Deque<Data>::copyDeque(const Deque<Data> &rhs)
{
	if (rhs.isEmpty())
	{
		return;
	}
	Node *t1 = rhs.start;
	Node *t2 = start = new Node();
	t2->info = t1->info;

	while (t1->next != NULL)
	{
		t2->next = new Node();
		t2->next->info = t1->next->info;
		t1 = t1->next;
		t2 = t2->next;
	}
	end = t2;
	_size = rhs.size();
}